"""
    给你一个字符串 s,找到 s 中最长的回文子串。
    如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

    Given a string s, return the longest palindromic substring in s.
"""

class Solution(object):
    def longestPalindrome(s):
        """
        :type s: str
        :rtype: str
        一：暴力算法，列举所有子串，每次进行回文判断，在此不展示
        二：中心扩散算法
            整体遍历一次，从首字母开始，先左右检测是单字母还是双字母的情况
            每次遍历从当前字母向两边扩散，每次扩散检测双侧字母，
            若不相等，则选择性的记录当前子串长度和子串起始位置
            紧接着开始下一个字母
        """
        if not len(s):
            return ''
        maxLength = 0
        maxIndex = 0
        for i, _ in enumerate(s):
            left, right = i, i
            while left != 0:
                if s[left-1] == s[i]:
                    left -= 1
                else:
                    break
            while right != len(s)-1:
                if s[right+1] == s[i]:
                    right += 1
                else:
                    break
            while left!=0 and right!=len(s)-1:
                if s[left-1] == s[right+1]:
                    left -= 1
                    right += 1
                else:
                    break
            if right-left+1 > maxLength:
                maxLength = right - left + 1
                maxIndex = left
        return s[maxIndex : maxIndex+maxLength]

print(Solution.longestPalindrome("ddabebas"))